package jzoffer.q0301duplicatearray;

/**
 * Author:   dengxin
 * Date:     2020/4/18 12:21 下午
 * 题目：
 * 在一个长度为n的数组里的所有数字都在[0,n-1]的范围内，数组中某些数字是重复的，
 * 但不知道有几个数字重复了，也不知道每个数字重复了几次，请找出数组中任意一个重复的数字
 *
 * 例：
 * 输入长度为7的数组：[2,3,1,0,2,5,3]
 * 输出：重复的数字2或3
 *
 * C++代码改写版
 *
 * 待完善，目前只能返回1个重复的数字
 */
public class DuplicateArray {

    public static void main(String[] args) {
        DuplicateArray duplicateArray = new DuplicateArray();
        duplicateArray.test1();
        duplicateArray.test2();
//        duplicateArray.test3();
        duplicateArray.test4();
        duplicateArray.test5();
        duplicateArray.test6();
    }

    int duplicate(int[] numbers, int length) {
        // 参数校验
        if (numbers ==null || length <=0) {
            System.out.println("Warning:数组为空");
            return -1;
        }
        for (int i=0; i<length; i++) {
            if (numbers[i] < 0 || numbers[i] > length-1) {
                System.out.println("Warning:数组元素值超出约定范围");
                return -1;
            }
        }

        // 查询重复参数
        for (int i=0; i<length; i++) {
            while(numbers[i] != i) {
                if (numbers[i] == numbers[numbers[i]]) {
                    return numbers[i];
                }
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return -1;
    }

    //===================测试代码===================

    private boolean contains(int[] array, int length, int number) {
        for (int i = 0; i < length; i++) {
            if (array[i] == number) {
                return true;
            }
        }
        return false;
    }

    private void test(String testName, int[] numbers, int lengthNumbers, int expectedDuplicateNum) {
        System.out.print(testName + " begins: ");

        int duplicateNum = duplicate(numbers, lengthNumbers);

        if (duplicateNum == expectedDuplicateNum) {
            System.out.println("Passed.");
        } else {
            System.out.println("Passed.");
        }
    }

    //重复数字是数组中最小数字
    private void test1() {
        int[] numbers = {2,1,3,1,4};
        int duplication = 1;
        test("Test1", numbers, numbers.length, duplication);
    }

    //重复数字是数组中最大数字
    private void test2() {
        int[] numbers = {2, 4, 3, 1, 4};
        int duplication = 4;
        test("Test2", numbers, numbers.length, duplication);
    }

    //数组存在多个重复数字
//    private void test3() {
//        int[] numbers = {2, 4, 2, 1, 4};
//        int[] duplication = {2, 4};
//        test("Test3", numbers, numbers.length, duplication, duplication.length, true);
//    }

    //没有重复数字
    private void test4() {
        int[] numbers = {3,5,1,4,0,2};
        int duplication = -1;
        test("Test4", numbers, numbers.length, duplication);
    }

    //无效的输入
    private void test5() {
        int[] numbers = {3,5,1,4,6,2};
        int duplication = -1;
        test("Test5", numbers, numbers.length, duplication);
    }

    //无效的输入
    private void test6() {
        int[] numbers = {};
        int duplication = -1;
        test("Test6", numbers, numbers.length, duplication);
    }
}
